// 101. 对称二叉树
// 给你一个二叉树的根节点 root ， 检查它是否轴对称。
// 示例 1：
// 输入：root = [1,2,2,3,4,4,3]
// 输出：true
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
//  队列实现迭代判断是否为对称二叉树：

 var isSymmetric = function(root) {
    if(root===null) return true;
    let queue=[];
    let res=[];
    queue.push(root.left);
    queue.push(root.right);
    let cur=null;
    // if(!root) return;
    while(queue.length!==0&&root!==null){
        let leftNode=queue.shift(root.left);
        let rightNode=queue.shift(root.right);
        if(leftNode===null&&rightNode===null){
            continue;
        }
        if(leftNode===null||rightNode===null||leftNode.val!==rightNode.val){
            return false;
        }
        queue.push(leftNode.left);
        queue.push(rightNode.right);
        queue.push(leftNode.right);
        queue.push(rightNode.left);
    }
    return true;
};

// 递归遍历 后序
// 1. 确定递归函数的参数和返回值
// 因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，
// 所以要比较的是两个树，参数自然也是左子树节点和右子树节点。
// 2. 确定终止条件
// 要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！
// 否则后面比较数值的时候就会操作空指针了。

// 节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）

// 左节点为空，右节点不为空，不对称，return false
// 左不为空，右为空，不对称 return false
// 左右都为空，对称，返回true
// 此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：

// 左右都不为空，比较节点数值，不相同就return false
// 此时左右节点不为空，且数值也不相同的情况我们也处理了。
// 3. 确定单层递归的逻辑
// 此时才进入单层递归的逻辑，单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。

// 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
// 比较内测是否对称，传入左节点的右孩子，右节点的左孩子。
// 如果左右都对称就返回true ，有一侧不对称就返回false 。
var isSymmetric = function(root) {
    //使用递归遍历左右子树 递归三部曲
    // 1. 确定递归的参数 root.left root.right和返回值true false 
    const compareNode=function(left,right){
        //2. 确定终止条件 空的情况
        if(left===null&&right!==null||left!==null&&right===null){
            return false;
        }else if(left===null&&right===null){
            return true;
        }else if(left.val!==right.val){
            return false;
        }
        //3. 确定单层递归逻辑
        let outSide=compareNode(left.left,right.right);
        let inSide=compareNode(left.right,right.left);
        return outSide&&inSide;
    }
    if(root===null){
        return true;
    }
    return compareNode(root.left,root.right);
};